package com.mzy;

import java.util.Arrays;

/**
 * @Author: codermzy
 * @Date: 2024/02/03/13:59
 * @Description:
 */
public class MergeSort {

   /* public static void sort(int[] arr) {
        process(arr, 0, arr.length - 1);
    }

    private static void process(int[] arr, int L, int R) {
        if (arr[L] == arr[R]) {
            return;
        }

        int mid = L + ((R - L) >> 1);
        process(arr, L, mid);
        process(arr, mid + 1, R);
        merge(arr, L, mid, R);
    }

    private static void merge(int[] arr, int L, int mid, int R) {
        int[] help = new int[R - L + 1];
        int i = 0; // help的下标

        int p1 = L;
        int p2 = mid + 1;

        while (p1 <= mid && p2 <= R) {
            // if(arr[p1] <= arr[p2]) {
            //     help[i] = arr[p1];
            //     p1++;
            // }else {
            //     help[i] = arr[p2];
            //     p2++;
            // }
            help[i++] = arr[p1] <= arr[p2] ? arr[p1++] : arr[p2++];
        }

        while (p1 <= mid) {
            help[i++] = arr[p1++];

        }

        while (p2 <= R) {
            help[i++] = arr[p2++];

        }

        for (i = 0; i < help.length; i++) {
            arr[L + i] = help[i];
        }
    }

    public static void mergeSort(int[] arr) {
        int N = arr.length;
        int mergeSize = 1;
        while (mergeSize < N) {
            int L = 0;

            while (L < N) {
                int M = L + mergeSize - 1;
                if (M >= N) break;

                int R = Math.min(M + mergeSize, N - 1);
                merge(arr, L, M, R);
                L = R + 1;
            }
            mergeSize <<= 1;
        }
    }*/

    // public static void thanLeftMin(int[] arr) {
    //
    // }

    /*
    public static void mergeSort2(int[] arr) {

        int N = arr.length;

        int mergeSize = 1;
        while (mergeSize < N) {
            int L = 0;

            while (L < N) {
                int M = L + mergeSize - 1;
                if (M >= N) break;

                int R = Math.min(M + mergeSize, N - 1);
                merge(arr, L, M, R);
                L = R + 1;
            }

            mergeSize <<= 1;
        }
    }
    */
    public static void main(String[] args) {
        Integer[] arr = {2, 1, 56, 8, 3, 7, 3, 9, 3, 89};
        Integer[] integers = mergeSort(arr);
        // sort(arr);
        System.out.println(Arrays.toString(integers));
    }

    private static void sort(Integer[] arr) {
        int n = arr.length;
        mergeSortInternal(arr, 0, n - 1);
    }

    private static void mergeSortInternal(Integer[] arr, int l, int r) {
        if (l >= r) return;
        int mid = l + ((r - l) >> 1);
        // l: 0  r: 4 mid: 2
        // l: 0  r: 2 mid: 1
        // l: 0  r: 1 mid: 0
        // l: 0  r: 0 mid: 0 return
        mergeSortInternal(arr, l, mid);
        mergeSortInternal(arr, mid + 1, r);


        merge(arr, l, mid, r);
    }

    private static void merge(Integer[] arr, int left, int mid, int right) {
        Integer[] help = new Integer[right - left + 1];

        int i = left;
        int j = mid + 1;
        int index = 0;
        while (i <= mid && j <= right) {
            if (arr[i] <= arr[j]) {
                help[index] = arr[i];
                i++;
            } else {
                help[index] = arr[j];
                j++;
            }
            index++;
        }

        while (i <= mid) {
            help[index] = arr[i];
            i++;
            index++;
        }

        while (j <= right) {
            help[index] = arr[j];
            j++;
            index++;

        }

        for (int p = 0; p < help.length; p++) {
            arr[left + p] = help[p];
        }
    }


    private static Integer[] mergeSort(Integer[] arr) {
        if (arr.length == 1) {
            System.out.println(arr[0]);
            return arr;
        }

        int mid = arr.length >> 1;

        Integer[] leftArr = Arrays.copyOfRange(arr, 0, mid);
        Integer[] rightArr = Arrays.copyOfRange(arr, mid, arr.length);

        Integer[] leftSorted = mergeSort(leftArr);
        Integer[] rightSorted = mergeSort(rightArr);

        Integer[] mergeArr = new Integer[leftArr.length + rightArr.length];

        int left = 0, right = 0, index = 0;
        while (left < leftSorted.length && right < rightSorted.length) {
            if (leftSorted[left] <= rightSorted[right]) {
                mergeArr[index++] = leftSorted[left++];
            } else {
                mergeArr[index++] = rightSorted[right++];
            }
        }

        while (left < leftSorted.length) {
            mergeArr[index++] = leftSorted[left++];
        }

        while (right < rightSorted.length) {
            mergeArr[index++] = rightSorted[right++];
        }
        return mergeArr;
    }


    private static Integer[] mergeSore(Integer[] arr) {
        if(arr.length == 1) {
            return arr;
        }

        int mid = arr.length >> 1;

        Integer[] leftArray = Arrays.copyOfRange(arr, 0, mid);
        Integer[] rightArray = Arrays.copyOfRange(arr, mid, arr.length);

        mergeSort(leftArray);
        mergeSort(rightArray);

        int i = 0, j = 0, k = 0;
        Integer[] newArray = new Integer[leftArray.length + rightArray.length];

        while (i < leftArray.length && j < rightArray.length){
            if(leftArray[i] <= rightArray[j]){
                newArray[k++] = rightArray[i++];
            }else {
                newArray[k++] = leftArray[j++];
            }
        }


        while (i < leftArray.length){
            newArray[k++] = leftArray[i++];
        }

        while (j < rightArray.length){
            newArray[k++] = rightArray[j++];
        }

        return newArray;
    }

    // private static Integer[] mergeSort(Integer[] arr) {
    //     if (arr.length == 1) {
    //         return arr;
    //     }
    //     int mid = arr.length >> 1;
    //
    //     // 1. 分解(divide) 把一个数组分成两个两个数组，以此类推，最终分成一个数组
    //     Integer[] leftArr = Arrays.copyOfRange(arr, 0, mid);
    //     Integer[] rightArr = Arrays.copyOfRange(arr, mid, arr.length);
    //
    //     Integer[] sortedLeft = mergeSort(leftArr);
    //     Integer[] sortedRight = mergeSort(rightArr);
    //
    //
    //     // 2. 合并(merge) 将两个子数组合并
    //     int left = 0, right = 0, index = 0;
    //     Integer[] mergeArr = new Integer[sortedRight.length + sortedLeft.length];
    //     while (left < sortedLeft.length && right < sortedRight.length) {
    //         if (sortedLeft[left] <= sortedRight[right]) {
    //             mergeArr[index] = sortedLeft[left];
    //             left++;
    //         } else {
    //             mergeArr[index] = sortedRight[right];
    //             right++;
    //         }
    //         index++;
    //     }
    //
    //     while (left < sortedLeft.length) {
    //         mergeArr[index] = sortedLeft[left];
    //         left++;
    //         index++;
    //     }
    //
    //     while (right < sortedRight.length) {
    //         mergeArr[index] = sortedRight[right];
    //         right++;
    //         index++;
    //     }
    //     return mergeArr;
    // }


}
